#include <string>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:

    //链表求和
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;//记录进位
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* head = nullptr;
        ListNode* tail = nullptr;

        while (cur1 || cur2)
        {
            int num1 = cur1 ? cur1->val : 0;
            int num2 = cur2 ? cur2->val : 0;
            int sum = num1 + num2 + carry;
            
            if (head == nullptr)
            {
                head = tail = new ListNode(sum % 10);
            }
            else 
            {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;

            if (cur1 != nullptr)
            {
                cur1 = cur1->next;
            }
            if (cur2 != nullptr)
            {
                cur2 = cur2->next;
            }
        }
        if (carry != 0)
        {
            tail->next = new ListNode(carry);
        }
        return head;
    }


    //括号的最大嵌套深度
    int maxDepth(string s) {
        int max_dep = 0;
        int hight = 0;
        for (auto ch : s)
        {
            if (ch == '(')
            {
                ++hight;
                max_dep = max(max_dep, hight);
            }
            else if (ch == ')')
            {
                --hight;
            }
        }
        return max_dep;
    }
};